package com.itheima.demo.sort;

public class QuickSort {
    public static void main(String[] args) {
        int[] arrs = {5,1,2,9,7,6,4,8,3,10,11,15,13,14,12};
        quicksort(arrs,0,arrs.length-1);
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i]+" ");
        }
    }

    private static void quicksort(int[] arrs, int left, int right) {

        if (right < left){
            return;//当右边的指针指向的索引值已经小于左边的指针时，就返回
        }

        int left0 = left;
        int right0 = right;
        int flag = arrs[left];//基准数，数组第一个元素

        while (left != right){

            //从右边开始找，值 大于 基准数并且索引值大于左边，就去找下一个
            while (arrs[right] >= flag && right>left){
                right--;
            }//从右边找到比基准数小的数时，就不会再进入循环，right会记住当前索引值，并停住

            //从左边开始找，值 小于 基准数并且索引值目前还是右边比较大时，就去找下一个
            while (arrs[left] <= flag && right>left){
                left++;
            }//退出循环就表示，从左边开始找的，比基准数还大的值已经找到，left已经记载了其索引

            //两个值已经确定，交换两个值
            int temp = arrs[left];
            arrs[left] = arrs[right];
            arrs[right] = temp;
        }
        //当left等于right时，交换当前位置的值和基准数
        int temp = flag;
        arrs[left0] = arrs[left];
        arrs[left] = flag;

        //递归调用自己，以基准数为标准分为两部分，递归调用排序
        quicksort(arrs,left0,right-1);//左边部分
        quicksort(arrs,left+1,right0);//右边部分


    }
}
